/**
 * 滑动窗口，每次s往后移一位。时间复杂度：O(m+(n−m)×Σ)
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const sLen = s.length,
    pLen = p.length;

  if (sLen < pLen) return [];

  // 维护两个26个字母的数组
  let sCount = new Array(26).fill(0),
    pCount = new Array(26).fill(0),
    res = [];

  // 如果数组第二位为1，则为b，为2，则有两个b
  for (let i = 0; i < pLen; i++) {
    sCount[s[i].charCodeAt() - "a".charCodeAt()]++;
    pCount[p[i].charCodeAt() - "a".charCodeAt()]++;
  }

  // 初始化p以后，判断s的前pLen位是否为p的异位词
  if (sCount.toString() === pCount.toString()) {
    res = [0];
  }

  // 判断s从第一位开始的每pLen位是否是p的异位词
  for (let i = 0; i < sLen - pLen; i++) {
    sCount[s[i].charCodeAt() - "a".charCodeAt()]--;
    sCount[s[i + pLen].charCodeAt() - "a".charCodeAt()]++;
    if (sCount.toString() === pCount.toString()) {
      res.push(i + 1);
    }
  }

  return res;
};

/**
 * 滑动窗口优化，时间复杂度减小。时间复杂度：O(n+m+Σ)
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const sLen = s.length,
    pLen = p.length;

  if (sLen < pLen) return [];

  // diffCount为不同的个数
  let diffCount = 0,
    countList = new Array(26).fill(0),
    res = [];

  // 初始化countList，如果p中含有字母，则countList字母位处减一；如果s中含有字母，则countList处加一
  for (let i = 0; i < pLen; i++) {
    countList[s[i].charCodeAt() - "a".charCodeAt()]++;
    countList[p[i].charCodeAt() - "a".charCodeAt()]--;
  }

  for (let i = 0; i < countList.length; i++) {
    // 若某一位不为0，则这一位不相等。不能简单求和，像s:aa,p:bb这种，求和会出错
    if (countList[i] !== 0) {
      diffCount++;
    }
  }

  if (diffCount === 0) res = [0];

  for (let i = 0; i < sLen - pLen; i++) {
    // countList[s[i].charCodeAt() - "a".charCodeAt()    这一位是将要滑动走的一位，所以countList这个字母位将要减1
    // 如果原本为0，减一以后，则不相等，diffCount加一
    // 如果原本为1，减一以后，则相等，diffCount减一
    // 其余情况，则只操作countList减一，因为不涉及到  相等>不相等或者不相等>相等  的状态变化
    if (countList[s[i].charCodeAt() - "a".charCodeAt()] === 0) {
      diffCount++;
    } else if (countList[s[i].charCodeAt() - "a".charCodeAt()] === 1) {
      diffCount--;
    }

    countList[s[i].charCodeAt() - "a".charCodeAt()]--;

    // countList[s[i + pLen].charCodeAt() - "a".charCodeAt()    这一位是将要滑动进的一位，所以countList这个字母位将要加1
    // 如果原本为0，加一以后，则不相等，diffCount加一
    // 如果原本为-1，加一以后，则相等，diffCount减一
    // 其余情况，则只操作countList加一，因为不涉及到  相等>不相等或者不相等>相等  的状态变化
    if (countList[s[i + pLen].charCodeAt() - "a".charCodeAt()] === 0) {
      diffCount++;
    } else if (countList[s[i + pLen].charCodeAt() - "a".charCodeAt()] === -1) {
      diffCount--;
    }

    countList[s[i + pLen].charCodeAt() - "a".charCodeAt()]++;

    if (diffCount === 0) {
      res.push(i + 1);
    }
  }

  return res;
};

findAnagrams("cbaebabacd", "abc");
